struct MCMF {
	int S, T;

	using u32 = unsigned int;
	using u64 = unsigned long long;
	const int INF = 0x3f3f3f3f;
	struct node {int to, w, c, nxt;};
	vector<vector<node>> G;
	queue<int> Q;
	vector<int> buc[32], h, dis, pos, cur, vis;
	int top, flow, cost, N;

	MCMF(int N_, int S_, int T_) : N(N_), S(S_), T(T_) {
		top = flow = cost = 0;
		G.resize(N + 1);
		h.resize(N + 1);
		vis.resize(N + 1);
		pos.resize(N + 1);
		cur.resize(N + 1);
		dis.resize(N + 1);
	} 

	void add_edge(int u, int v, int w, int c) {
		G[u].emplace_back(node{v, w, c, G[v].size()});
		G[v].emplace_back(node{u, 0, -c, (int)G[u].size() - 1});
	}

	void spfa() {
		fill(h.begin(), h.end(), INF);
		h[S] = 0; vis[S] = true;
		Q.push(S);

		while (!Q.empty()) {
			int u = Q.front();
			Q.pop();
			vis[u] = false;

			for (auto &[v, w, c, rev] : G[u]) {
			 	if (h[v] > h[u] + c && w) {
          h[v] = h[u] + c;
          if (!vis[v]) {
          	vis[v] = true;
          	Q.push(v);
          }
        }
			}
		}
	}

	int get_high_32(u32 x) {
		return x ? 32 - __builtin_clz(x) : 0;
	}

	int get_high_64(u64 x) {
		return x ? 64 - __builtin_clzll(x) : 0;
	}

	template<class T> 
	int get_high_bit(T x) {
		return sizeof(T) == 4 ? get_high_32(x) : get_high_64(x);
	}

	void insert(int x) {
		int k = get_high_bit(dis[x] ^ dis[top]);
		pos[x] = buc[k].size();
		buc[k].push_back(x);
	}

	void remove(int x) {
		int k = get_high_bit(dis[x] ^ dis[top]);
		buc[k][pos[x]] = buc[k].back();
    pos[buc[k].back()] = pos[x];
    buc[k].pop_back();
	}

	void update(int x, int k) {
		remove(x);
		dis[x] = k;
		insert(x);
	}

	void removemin() {
    remove(top), top = 0;
    if (buc[0].size()) {
    	return void(top = buc[0][0]);
    }
    for (int i = 1; i <= 31; i++) {
      if (buc[i].empty()) {
      	continue;
      }
      for (int j : buc[i]) {
        if (dis[j] < dis[top]) {
        	top = j;
      	}
      }
      for (int j : buc[i]) {
      	insert(j);
      }
      return buc[i].clear();
    }
	}

	bool dijkstra() {
		fill(dis.begin(), dis.end(), INF);
    dis[top = S] = 0;
    for (int i = 0; i <= 31; i++) {
    	buc[i].clear();
    }
    for (int i = 1; i <= N; i++) {
    	insert(i);
    }
    for (; top; removemin()) {
      for (auto [v, w, c, rev] : G[top]) {
        if (dis[v] > dis[top] + c + h[top] - h[v] && w) {
        	update(v, dis[top] + c + h[top] - h[v]);
      	}
      }
    }
    return dis[T] != INF;
	}

	int dfs(int u, int flow) {
    if (u == T) {
    	return flow;
    }
    int used = 0;
    vis[u] = true;
    for (int &i = cur[u]; i < (int)G[u].size(); i++) {
      auto [v, w, c, rev] = G[u][i];
      if (!vis[v] && dis[v] == dis[u] + c + h[u] - h[v] && w) {
        int ret = dfs(v, min(flow - used, w));
        used += ret;
        G[u][i].w -= ret;
        G[v][rev].w += ret;
        if (used == flow) break;
      }
    }
    vis[u] = false;
    return used;
	}

	pair<int, int> work() {
    spfa();
    while (dijkstra()) {
      fill(vis.begin(), vis.end(), 0);
      fill(cur.begin(), cur.end(), 0);
      int ret;
      while ((ret = dfs(S, INF))) {
      	flow += ret;
      	cost += ret * (dis[T] + h[T]);
      }
      for (int i = 1; i <= N; i++) {
      	h[i] += dis[i];
	  	}
	  }
	  return {flow, cost};
	}
};